\section{Problema 1}

\subsection{Enunciado}

Como todos sabemos, la forma m\'as segura de saber si alguien te quiere es recurriendo al m\'etodo cientificamente
probado de las margaritas.
Esto es, se toma una margarita y se repite sucesivamente la frase ”Me quiere” y ”No me quiere”, mientras se procede a
sacar un p\'etalo de la margarita. La frase que corresponde al ultimo p\'etalo indica si el amor es correspondido o no.\\ \\

Como no nos gusta perder, queremos tener un mecanismo para asegurarnos tener una respuesta ”Me quiere” siempre.
Para esto nos tenemos que asegurar que todas las margaritas tengan un n\'umero impar de p\'etalos. Esto lo lograremos
sac\'andole un p\'etalo a las flores con un n\'umero par de p\'etalos.\\ \\

Tenemos luego un campo rectangular de margaritas, cuyo ancho es W y altura es H. Hay una margarita en cada
posici\'on del campo (w, h) con w = 1, 2, . . . , w y h = 1, 2, . . . , h. Pacientemente hemos contadoo la cantidad de p\'etalos de
cada margarita, siendo este P [w, h].\\ \\

Se comenzar\'a desde la posici\'on (1, 1) y deber\'as pasar por todas las margaritas con n\'umero par de p\'etalos.
Si tu posici\'on es (w, h), s\'olo pod\'es realizar tres movimientos: hacia abajo (h + 1), hacia izquierda (w - 1) y hacia la
derecha (w + 1).\\ \\

La tarea es computar el m\'inimo n\'umero de movimientos necesario para pasar por todas las margaritas (posiciones)
con n\'umero par de p\'etalos.\\ \\

Analizar la complejidad temporal usando el modelo uniforme y expresarla en funci\'on de w, h. Se debe encontrar un
algoritmo con complejidad menor o igual que O(w * h).


\subsection{Correctitud}
Como hay que recorrer todos los casilleros y no se puede subir, quiere decir que en la primer fila si o si tenemos que ir hasta el último casillero con número par. Una vez allí sólo nos queda bajar a la siguiente fila. ¿Podemos ir hacia la izquierda o hacia la derecha? Si, se podría, y el camino sería diferente, pero no la cantidad de pasos. ¿Por qué? porque la distancia entre todos los casilleros es de 1, no hay pasos que no tengan un peso de 1, da lo mismo primero bajar y luego moverse hacia un costado que primero moverse hacia un costado y luego bajar.

Una vez en la segunda fila tenemos que recorrer todos los casilleros con número par, si nos encontramos a la derecha del último o a la izquierda del primero la solución consiste en avanzar en la dirección correcta hasta llegar al último. En caso contrario habrá que repetir algunos pasos, avanzando primero a la izquierda y luego a la derecha (o al revés, lo que sea menor). Y luego bajar a la tercer fila desde el extremo izquierdo (primer casillero con número par) o desde el extremo derecho (último casillero con número par), lo que nos da 1 sola posibilidad de entrada a la fila 2, y 2 posibilidades de salida (extremo izquierdo y extremo derecho).

En las filas siguientes tenemos 2 posibilidades de entrada (extremo izquierdo y extremo derecho de la fila anterior), a partir de ahí debemos calcular la cantidad mínima de pasos para recorrer todos los casilleros con número par de la fila y brindar 2 posibilidades de salida (extremo izquierdo y extremo derecho). Las únicas que nos interesan son las 2 de salida, pues de las 2 de entrada elegimos la que nos brinde el costo mínimo para la salida en cuestión.

Por lo tanto se plantean las siguientes ecuaciones:

\begin{itemize}
	\item $Ci(f) = min( Ci(f-1) + Rii, Cd(f-1) + Rdi ) + 1$
	\item $Cd(f) = min( Ci(f-1) + Rid, Cd(f-1) + Rdd ) + 1$
\end{itemize}

Donde:

\begin{itemize}
 \item Ci: El costo de bajar por izquierda.
 \item Cd: El costo de bajar por derecha.
 \item Rii: El costo de recorrer todos los casilleros con pétalos pares desde la salida izquierda de la fila anterior a la salida izquierda de la fila actual.
 \item Rid: El costo de recorrer todos los casilleros con pétalos pares desde la salida izquierda de la fila anterior a la salida derecha de la fila actual.
 \item Rdi: El costo de recorrer todos los casilleros con pétalos pares desde la salida derecha de la fila anterior a la salida izquierda de la fila actual.
 \item Rdd: El costo de recorrer todos los casilleros con pétalos pares desde la salida derecha de la fila anterior a la salida derecha de la fila actual.
\end{itemize}

La solución al problema es $min( Ci(f), Cd(f) )$ donde $f$ es la última fila con algún número par.

Se utiliza una matriz para almacenar los costos de las filas, y se empieza a calcular desde la primer fila hacia la última.


\subsection{Pseudocódigo}
% \begin{verbatim}
%  rango <- matriz( 2 columnas, h filas );
%  costos <- matriz( 2 columnas, h filas );
% 
%  por cada fila:
%   rango( fila ) <- calcular la primera y última flor con pétalos par;
%  
%  costos( fila 1 ) <- <INFINITO, ( rango( fila 1, derecha ) ) >;
% 
%  por cada fila desde la segunda:
%   costos( fila ) <- calcularCosto( costos, rango );
% 
%  return menorPeso( ultima fila con candidatos );
% \end{verbatim}

\begin{algorithm}[H]
  \caption{calcularExtremos(Entero $fila$, Matriz $campo$)}
  \begin{algorithmic}[1]
    \STATE Entero primero
    \STATE Entero ultimo
    \STATE Boolean hayPrimero
    \FOR{$i$ de 1 hasta $h$}
      \IF{(esPar(campo[f][i]) y nohayPrimero)}
	\STATE primero = ultimo = i
      \ELSE 
	\STATE ultimo = i 
      \ENDIF
    \ENDFOR
    \RETURN (primero, ultimo)
  \end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{resolver(Entero $h$, Entero $w$, Matriz $campo$)}
\begin{algorithmic}[1]
	\STATE Matriz $rango$ $\leftarrow $  Matriz($h$, 2);
	\STATE Matriz $costos$ $\leftarrow $  Matriz($h$, 2);
	\STATE Entero $ultimaFilaValida \leftarrow 1$; 
	\STATE
	\FOR{$fila$ de 1 hasta $h$}
		\STATE $rango[fila] \leftarrow$ calcularExtremos($fila$, $campo$);
	\ENDFOR
	\STATE
	\STATE $costos[1][IZQUIERDA] \leftarrow +\infty$;
	\STATE $costos[1][DERECHA] \leftarrow rango[1][DERECHA]$;
	\STATE
	\FOR{$fila$ de 2 hasta $h$}
		\STATE $costos[fila] \leftarrow$ calcularCostos($w$, $fila$, $campo$);
		\IF{rangoVálido($rango[fila]$)}
			\STATE $ultimaFilaValida \leftarrow fila$;
		\ENDIF
	\ENDFOR
	\STATE
	\RETURN mínimo($costos[ultimaFilaValida])$;
	%\RETURN mín($costos[ultimaFilaValida][IZQUIERDA]$, $costos[ultimaFilaValida][DERECHA]$);
	%\RETURN mínimo(costos[ultimaFilaValida][IZQUIERDA], costos[ultimaFilaValida][DERECHA]);
\end{algorithmic}
\end{algorithm}

\subsection{An\'alisis de Complejidad}
\begin{enumerate}
	\item Por cada fila de flores encontramos la primer y última flor con una cantidad de pétalos par, esto lo podemos hacer en $O(w)$ y lo hacemos h veces, de modo que es $O(w \cdot h)$.
	\item Calcular los costos de la primer fila es trivial y se realiza en $O(1)$.
	\item Por cada fila de flores calculamos el costo de recorrerla, calcular el costo lleva $O(1)$, y lo hacemos h veces, de modo que es $O(h)$.
	\item Elegimos el menor costo de la última fila con al menos una flor de pétalos par, esto lleva $O(1)$.
\end{enumerate}

Total: $O(w \cdot h) + O(1) + O(h) + O(1) = O(w \cdot h)$.

\subsection{Mediciones}
Consideramos mejor caso al caso en el que el tamaño de la entrada sólo se refleja en el ancho del campo (w=tamaño, h=1), pues de esta manera se evita llamar (en la implemtanción) a la función {\bf costo}.

Consideramos peor caso al caso en el que el tamaño de la entrada sólo se refleja en el alto del campo (w=1, h=tamaño), pues de esta manera se logra llamar (en la implementación) {\bf siempre} a la funcón {\bf costo}.

Los siguientes datos se tomaron utilizando el ``profiler'' gprof, para el mejor caso con optimizaciones:
\begin{verbatim}
  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 63.47      2.32     2.32    62500     0.00     0.00  resolver(Matriz const&)
 36.66      3.66     1.34        1     1.34     3.66  generarMejorCaso(...)
   ...       ...      ...      ...      ...      ...  ...
\end{verbatim}

Para el peor caso con optimizaciones:

\begin{verbatim}
  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 61.27     33.05    33.05 1953093750   0.00     0.00  costo(...)
 35.63     52.28    19.22    62500     0.00     0.00  resolver(Matriz const&)
   ...       ...      ...      ...      ...      ...  ...
\end{verbatim}

Si bien la cantidad de llamadas a la función {\bf resolver} es la misma (62.500 problemas diferentes), para el peor caso se realizan 1.953.093.750 llamadas a la función {\bf costo}, lo cual se lleva el 61,27\% del tiempo de ejecución del programa (unos 33,05 segundos). Además el primer ciclo de la función {\bf resolver} se ejecuta de manera más eficiente en el primer caso, y del último ciclo sólo se realiza la inicialización y la comprobación de la condición.

\mifig{problema1/mejor-caso}{Mejor caso}
\mifig{problema1/peor-caso}{Peor caso}
\mifig{problema1/mejor-peor-aleatorio}{Comparación de los distintos casos}

\newpage